/**
 * FileName: TestBalanceR.c
 * ---------------------------------------------------------------------
 * 这个文件旨在为`balanceR`提供骨架代码。
 *
 *
 */

#include <assert.h>
#include <stdlib.h>

//见Item.h
typedef struct Item* Item;
typedef char Key;
typedef int Value;
#define key(A) (A->key)
#define value(A) (A->value)
#define less(A, B) (A < B)
#define eq(A, B) (A == B)
#define exch(A, B) { Item t = A; A = B; B = t; }
#define NULLitem NULL

struct Item {
    Key key;
    Value value;
};

typedef struct STnode* link;

struct STnode {
    Item item;
    link l;
    link r;
    int N;
};

link head;
link z;

/***********************************辅助函数部分*******************************/
link NEW(Item item, link l, link r, int N) {
    link x = malloc(sizeof(*x));
    x->item = item;
    x->l = l;
    x->r = r;
    x->N = N;
    return x;
}

int size(link h) {
    if (h == z) {
        return 0;
    }else {
        return h->N;
    }
}

void update_N(link h) {
    if (h != z) {
        h->N = size(h->l)+size(h->r)+1;
    }
}

/**
 *
 * ---------------------------------------------------------------------------------------------------------
 * Program 12.11 Rotations in BSTs
 * ---------------------------------------------------------------------------------------------------------
 * These twin routines perform the rotation operation on a BST.
 * A right rotation makes the old root the right subtree of the new root (the old left subtree of the root).
 * A left rotation makes the old root the left subtree of the new root (the old right subtree of the root).
 *
 * For implementations where a count field is maintained in the nodes
 * (for example, to support `select`, as we will see in Section 14.9),
 * we need also to exchange the `count` fields in the nodes involved in the rotation (see Exercise 12.72).
 *
 * ---------------------------------------------------------------------------------------------------------
 * 右旋
 * @param h
 * @return
 * 涉及3个链接和两个节点
 *
 * 这两个节点分别是：
 * - 旧根h
 * - 新根x，即h的左孩子
 *
 * 显然有：h的键大于等于x的键
 *
 * 这3个链接分别是：
 * - 原指向旧根的链接；
 * - 旧根指向新根的链接h->l;
 * - 新根的右孩子节点x->r;
 *
 * 右旋的本质是将旧根的左链接逆向
 */
link rotR(link h) {
    link x = h->l;
    h->l = x->r;
    x->r = h;
    update_N(h);
    update_N(x);
    return x;
}

/**
 * 左旋
 * @param h
 * @return
 * -----------------------------------------
 * 涉及3个链接和两个节点
 *
 * 这两个节点分别是：
 * - 旧根h
 * - 新根x，即h的右孩子
 *
 * 显然有：h的键小于等于x的键
 *
 * 这3个链接分别是：
 * - 原指向旧根的链接；
 * - 旧根指向新根的链接h->r;
 * - 新根的左孩子节点x->r;
 *
 * 左旋的本质是将旧根的右链接逆向
 */
link rotL(link h) {
    link x = h->r;
    h->r = x->l;
    x->l = h;
    update_N(h);
    update_N(x);
    return x;
}

/**
 * 在底部插入项
 * @param h
 * @param item
 * @return
 * -------------------------------------------
 * insertT是insertR的自适应版本
 *
 */
link insertR(link h, Item item) {
    if (h == z) {
        return NEW(item, z, z, 1);
    }
    Key v = key(item);
    Key t = key(h->item);
    if (less(v, t)) {
        h->l = insertR(h->l, item);
    }else {
        h->r = insertR(h->r, item);
    }
    (h->N)++;
    return h;
}

/**
 * BST的划分操作：将子树中键值第k小的元素移动到根部
 * @param h 当前子树的根节点
 * @param k 目标元素在当前子树中的零基索引（例如 k=0 表示最小元素）
 * @return 经过划分后，以键值第k小的元素为根的新子树的根节点
 * ---------------------------------------------------------------------------------------------------
 * Program 12.14 Partitioning of a BST
 * ---------------------------------------------------------------------------------------------------
 * 思路：
 * partR是selectR的自适应版本，思想是将最近（或当前）操作的元素（即第k小的元素）提升到根部。
 * 这样做能够将树以该元素为“枢轴”进行划分，使得小于它的元素都在左子树，大于它的元素都在右子树。
 *
 */
link partR(link h, int k) {
    int t = h->l == z ? 0 : size(h->l);
    if (t < k) {
        h->r = partR(h->r, k - t - 1);
        h = rotL(h);
    }
    if (t > k) {
        h->l = partR(h->l, k);
        h = rotR(h);
    }
    return h;
}

/**
 * Program 13.1 Balancing a BST
 * ------------------------------------------------------------------------------------------------------------------
 * This recursive function puts a BST into perfect balance, using the partitioning function partR from Program 12.14.
 * We partition to put the median node at the root, then (recursively) do the same for the subtrees.
 * ------------------------------------------------------------------------------------------------------------------
 * 全局平衡操作递归版
 * @param h
 * @return
 */
link balanceR(link h) {
    //TODO
    return h;
}

/***********************************接口部分*******************************/
void STinit() {
    z = NEW(NULLitem, 0, 0, 0);
    head = z;
}

int STcount() {
    return head->N;
}

/**
 * STinsert
 * @param item
 * 思路：
 * - 在底部插入
 */
void STinsert(Item item) {
    // 在底部插入(普通版本)
    head = insertR(head, item);
}

/***********************************测试部分*******************************/
Item create_item(Key key, Value value) {
    Item x = malloc(sizeof(*x));
    x->key = key;
    x->value = value;
    return x;
}

void test_balanceR() {
    STinit();
    assert(STcount() == 0);

    STinsert(create_item('A', 1));
    STinsert(create_item('B', 2));
    STinsert(create_item('C', 3));
    STinsert(create_item('D', 4));
    STinsert(create_item('E', 5));

    assert(STcount() == 5);
    assert(key(head->item) == 'A');

    head = balanceR(head);

    assert(key(head->item) == 'C');


}

int main(int argc, char *argv[]) {
    test_balanceR();
    return 0;
}